package leetcode.editor.cn.q1_300.q;

import java.util.ArrayList;
import java.util.List;

/**
 * @author qidi
 * @date 2021-11-02 09:08:52
 */
class Q0022_GenerateParentheses {

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public List<String> generateParenthesis(int n) {
            List<String> res = new ArrayList<>();
            process(n * 2, res, "");
            return res;
        }

        private void process(int n, List<String> res, String s) {
            if (!check(s, n)) return;

            if (s.length() == n) {
                res.add(s);
                return;
            }

            process(n, res, s + "(");
            if (s.length() != 0) {
                process(n, res, s + ")");
            }
        }

        private boolean check(String s, int n) {
            int left = 0;
            for (int i = 0; i < s.length(); i++) {
                if (left < 0) return false;
                if (s.charAt(i) == '(') {
                    left++;
                } else {
                    left--;
                }
            }
            return s.length() == n && left == 0 || s.length() < n && left >= 0 && left <= n - s.length();
        }
    }
//leetcode submit region end(Prohibit modification and deletion)


    public static void main(String[] args) {
        Solution solution = new Q0022_GenerateParentheses().new Solution();
        System.out.println(solution.generateParenthesis(4));
        System.out.println(solution.generateParenthesis(3));
        System.out.println(solution.generateParenthesis(2));
        System.out.println(solution.generateParenthesis(1));
    }
}